//题目:
// 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
// L0 → L1 → … → Ln - 1 → Ln
// 请将其重新排列后变为：
// L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
// 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

#include<iostream>

using namespace std;
//代码:
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    void reorderList(ListNode* head) {
        //将链表一分为二，偶数结点，则n/2+1  n/2-1；奇数结点，则n/2+1  n/2
        // int n=0;
        // ListNode* cur=head,*parent=nullptr;
        // //数出该链表有多少个结点
        // while(cur){
        //     cur=cur->next;
        //     n++;
        // }
        // cur=head;
        // int steps=n/2+1;
        // while(steps>=1){
        //     parent=cur;
        //     cur=cur->next;
        //     steps--;
        // }
        // //跳出循环后，cur是第二组的新节点
        // parent->next=nullptr;
        // //对第二组结点逆置,新的头结点是newhead
        // ListNode* newhead=nullptr;
        // while(cur){
        //     ListNode* next=cur->next;
        //     //头插
        //     cur->next=newhead;
        //     newhead=cur;
        //     //更新cur
        //     cur=next;
        // }
        // //将第二组的结点插入第一组中
        // cur=head;
        // while(newhead){
        //     ListNode* next=cur->next;
        //     //插入结点
        //     cur->next=newhead;
        //     //更新newhead
        //     newhead=newhead->next;
        //     //结点归位
        //     cur->next->next=next;
        //     //更新cur
        //     cur=next;
        // }

        //法二：同思路，不同解法
        //1.快慢指针找中间节点
        ListNode* fast=head,*slow=head;
        while(fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        //出来后，无论有偶、奇数个节点，则slow都处于第n/2个结点位置
        //2.逆置slow后面的所有结点————头插法
        //ListNode* head2=new ListNode(0);//引入一个虚拟头结点
        ListNode* cur=slow->next,*newhead=nullptr;
        while(cur){
            ListNode* next=cur->next;
            //头插
            cur->next=newhead;
            newhead=cur;
            //更新cur
            cur=next;
        }
        slow->next=nullptr;//将链表断开
        
        //3.将head和head2插到一起
        cur=head;
        while(newhead){
            ListNode* next=cur->next;
            //插入结点
            cur->next=newhead;
            //更新newhead
            newhead=newhead->next;
            //结点归位
            cur->next->next=next;
            //更新cur
            cur=next;
        }
    }
};